Pattern matching or comparison schemes have many applications, such as identifying machine parts in a manufacturing context, and the reading of addresses in a mail-sorting context. The above-mentioned applications are among the simpler uses of such comparisons, because, in the case of machine parts, the number of different parts is finite, and their shapes are, in general, relatively simple; the text reading context has only 26 letters and ten digits to identify, although the number of permutations of machine printing is large.
More complex types of comparisons are those involving differentiation among items which are similar, but not identical, especially when the conditions under which the images are formed is not uniform. When the images are of biological specimens, the variability of the images may be very large. One such aspect of image matching is that of matching the retinal patterns of subjects for identification. Another use is that of identification of fingerprints by comparison with file fingerprints.
Fingerprints are very rich in information content. There are two major types of information in a fingerprint. First is the ridge flow information, and second is the specific features or minutiae (minutia) of the fingerprint. As used herein, the term "minutia" is used to denote both the singular and plural. Fingerprints uniquely identify an individual based on their information content. Information is represented in a fingerprint by the minutia and their relative topological relationships. The number of minutia in a fingerprint varies from one finger to another, but, on average, there are about eighty (80) to one hundred and fifty (150) minutia per fingerprint. In the fingerprint context, a large store of fingerprints exists in law enforcement offices around the country. These fingerprints include files of fingerprints of known individuals, made in conjunction with their apprehension or for some other reason such as security clearance investigation or of obtaining immigration papers, often by rolling the inked fingers on cards, and also includes copies of latent fingerprints extracted from crime scenes by various methods. These reference fingerprints are subject to imperfections such as overinking, which tends to fill in valleys in fingerprints, and underinking, which tends to create false ridge endings, and possibly both overinking and underinking in different regions of the same fingerprint image. Smudging and smears occur at different places in the fingerprint due to unwanted movement of the finger, or uneven pressure placed on the finger, during the rolling process. The stored fingerprints are also subject to deterioration while in storage, which may occur, for instance, due to fading of the older images, or due to stains. Furthermore, the wide variation in the level of experience among fingerprint operators, and the conditions under which the fingerprint is obtained, produces wide variation in quality in the fingerprint images. Similar effects occur due to the variation of the scanning devices in cases of live scanning of fingerprints.
Matching of fingerprints in most existing systems relies for the most part on comparison of cores and deltas as global registration points, which tends to make the comparisons susceptible to errors due to the many sources of distortion and variations listed above, which almost always occur due to the various different inking, storage and preprocessing conditions which may be encountered.
As described at pages 164-191 of the text Advances in Fingerprint Technology, by Henry C. Lee and R. E. Guenssten, published by Elsevier in 1991, efforts have been underway for a long time to automate fingerprint identification, because manual search is no longer feasible due to the large number of reference files. The effort to automate fingerprint identification involves two distinct areas, namely (a) that of fingerprint scanning and minutia identification, and (b) comparison of lists of minutia relating to different fingerprints in order to identify those which match. Large files of reference fingerprints have been scanned, and minutia lists in digital form obtained therefrom, either by wholly automated equipment, or with semiautomated equipment requiring human aid. While not all problems in scanning of fingerprints and detection of minutia have been solved, it appears that the matching problem is the more pressing at this time.
The matching or search subsystem constitutes the most critical component of any Automated Fingerprint Identification System (AFIS). Its performance establishes the overall system matching reliability (the probability of declaring the correct mate, if one exists in the database), match selectivity (the average number of false candidates declared in each search attempt), and throughput, which is particularly important in large database systems. The unique identification of fingerprints is usually performed using the set of minutia contained in each fingerprint. For each fingerprint, these minutia form a minutia map.
FIG. 1a illustrates a particular skeletonized fingerprint impression, number F0048.sub.-- 04, from the National Institute of Standards and Technology (NIST) database 4, resulting from a proper inking procedure, while FIG. 1b illustrates the same skeletonized fingerprint, resulting from underinking and some smudges in the underlying impression. As a result of the different conditions under which the impressions of FIGS. 1a and 1b were made, at least some of the minutia, represented by dots in FIGS. 1a and 1b, are different, and differently located. These differences make it clear that a matching scheme must be particularly robust if it is to reliably identify an unknown or search fingerprint with a reference fingerprint without generating an excessive number of false positives.
An improved search or matching system is desired, which provides high match reliability, low match selectivity, and high system throughput in a large database context.